import java.util.List;

/**
 * Created by L.jp
 * Description:给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
 * User: 86189
 * Date: 2022-05-15
 * Time: 16:00
 */
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val=val;
    }
  }
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        /*使用快慢指针*/
       //借助一个空的节点作为新的表头，如果要删除的是表头，那么直接返回这个新节点的next就行
//        ListNode res=new ListNode(-1);
//        res.next=head;
//        ListNode pre=res;
//        ListNode fast=head;
//        ListNode slow=head;
//        //先让快指针走n步
//        while (n>0){
//            fast=fast.next;
//            n--;
//        }
//        //找到倒数第n个节点和他的前一个节点
//        while (fast!=null){
//            fast=fast.next;
//            pre=slow;
//            slow=slow.next;
//        }
//        //此时slow就是倒数第n个节点，pre就是他的前驱节点
//        pre.next=slow.next;
//        return res.next;
        
        /*使用len-n的方法*/
        //还是要借助虚拟节点
        ListNode res=new ListNode(-1);
        res.next=head;
        ListNode pre=res;
        ListNode cur=head;
        int len=0;
        while (cur!=null){
            len++;
            cur=cur.next;
        }
        cur=head;
        //找到第n-k个位置。从头结点的下一个开始
        for(int i=0;i<len-n;i++){
            pre=cur;
            cur=cur.next;
        }
        //cur的位置就是要删除的位置
        pre.next=cur.next;
        return  res.next;
    }

}
